public class MinimumWindowSubstring {
    // 最小覆盖子串 https://leetcode.cn/problems/minimum-window-substring/submissions/673994170/

    public String minWindow(String ss, String tt) {
        //使用数组来模拟哈希表
        int[] hash1=new int[128];//能用数组就用数组,尽量不用哈希表
        int kinds=0;//标记数组中有效元素的种类

        char[] s=ss.toCharArray();
        char[] t=tt.toCharArray();
        for(char ch:t) {
            if(hash1[ch]==0) kinds++;
            hash1[ch]++;
        }

        int[] hash2=new int[128];//用来统计窗口内字符的频次
        int minLen=Integer.MAX_VALUE,begin=-1;//begin是最终结果的起始位置
        for(int left=0,right=0,count=0;right<s.length;right++) {
            char in=s[right];
            hash2[in]++;//进窗口
            // 判断
            if(hash2[in]==hash1[in]) count++;//维护count
            while (kinds==count) {
                //更新结果
                if(right-left+1 < minLen) {
                    begin=left;
                    minLen=right-left+1;
                }
                char out=s[left++];//出窗口
                if(hash2[out]==hash1[out])count--;//维护count
                hash2[out]--;

            }
        }
        // 返回结果
        if(begin==-1) return new String();
        else return ss.substring(begin,begin+minLen);
    }
}
